﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class PouringWater
    {
        enum Doit { EA, EB, FA, FB, AB, BA };
        public PouringWater()
        {
            
            int testCase = Int32.Parse(Console.ReadLine());
            while (testCase-- > 0)
            {
                int sizeA = Int32.Parse(Console.ReadLine());
                int sizeB = Int32.Parse(Console.ReadLine());
                int sizeC = Int32.Parse(Console.ReadLine());
                if (sizeC == 0)
                {
                    Console.WriteLine("0");
                    continue;
                }
                byte[,] checkBoard = new byte[sizeA + 1, sizeB + 1];
                Queue<int[]> q = new Queue<int[]>();
                q.Enqueue(new int[3] { 0, 0, 0 });
                checkBoard[0, 0] = 1;
                int output = -1;
                while (q.Count > 0)
                {
                    int[] vessel = q.Dequeue();
                    for (int i = 0; i < 6; i++)
                    {
                        int[] newVessel = new int[3] { vessel[0], vessel[1], vessel[2] + 1 };
                        bool result = DoSomething((Doit)i, ref newVessel, sizeA, sizeB);
                        if (result)
                        {
                            if (newVessel[0] == sizeC || newVessel[1] == sizeC)
                            {
                                output = newVessel[2];
                                q.Clear();
                                break;
                            }
                            else if (checkBoard[newVessel[0], newVessel[1]] == 0)
                            {
                                q.Enqueue(newVessel);
                                checkBoard[newVessel[0], newVessel[1]] = 1;
                            }
                        }
                    }
                }
                Console.WriteLine(output);
            }
        }
        private bool DoSomething(Doit mode, ref int[] vessel, int sizeA, int sizeB)
        {
            switch (mode)
            {
                case Doit.EA:
                    if(vessel[0] == 0)
                    { return false;}
                    else 
                    {
                        vessel[0] = 0;
                        return true;
                    }
                case Doit.EB:
                    if(vessel[1] == 0)
                    { return false;}
                    else 
                    {
                        vessel[1] = 0;
                        return true;
                    }
                case Doit.FA:
                    if(vessel[0] == sizeA)
                    { return false;}
                    else 
                    {
                        vessel[0] = sizeA;
                        return true;
                    }
                case Doit.FB:
                    if(vessel[1] == sizeB)
                    { return false;}
                    else 
                    {
                        vessel[1] = sizeB;
                        return true;
                    }
                case Doit.AB:
                    if(vessel[0] == 0)
                    {
                        return false;
                    }
                    else if(vessel[1] == sizeB)
                    {
                        return false;
                    }
                    else
                    {
                        vessel[1] = vessel[1] + vessel[0];
                        int overflow = vessel[1] - sizeB;
                        if (overflow > 0)
                        {
                            vessel[1] -= overflow;
                            vessel[0] = overflow;
                        }
                        return true;
                    }
                case Doit.BA:
                    if (vessel[1] == 0)
                    {
                        return false;
                    }
                    else if (vessel[0] == sizeA)
                    {
                        return false;
                    }
                    else
                    {
                        vessel[0] = vessel[0] + vessel[1];
                        int overflow = vessel[0] - sizeA;
                        if (overflow > 0)
                        {
                            vessel[0] -= overflow;
                            vessel[1] = overflow;
                        }
                        return true;
                    }
                default:
                    return false;
            }
        }
    }
}
